package com.kaigejava.sparsearr;

/**
 * 稀疏数组demo
 * 二维数组转稀疏数组的demo
 * 五子棋：
 * 棋盘大小：11*11的
 * 0：表示没有棋子
 * 1：表示 黑色
 * 2：表示 蓝色
 */
public class ArrayToSparseArrayDemo {

    public static void main(String[] args) {
        int chessArr[][] = init();
        //将二维数组转换成稀疏数组
        int [] [] sparseArr =  arrchangeSparseArr(chessArr);
    }

    /**
     * 将二维数组转换成稀疏数组
     * 1:遍历原始的二维数组，得到有效数据的个数。sum
     * 2：根据sum就可以创建稀疏数组 sparseArr int [sum+1][3];
     * 3：将二维数组的有效数据存入到 稀疏数组
     *      3.1：稀疏数组的第一行记录元素数组的 行 列 有效数据总数
     *      3.2：从第二行开始，记录有效数据的 行 列 值
     * @param chessArr
     */
    public static int[][] arrchangeSparseArr(int[][] chessArr) {
        //1:
        int sum = 0;
        int size = chessArr.length;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if(chessArr[i][j] != 0){
                    sum++;
                }
            }
        }

        //2：根据sum就可以创建一个稀疏数组
        int [] [] sparseArr = new  int[sum+1][3];
        //3:给稀疏数组赋值
        //3.1：给稀疏数组第一行赋值
        sparseArr = initSparseArrFrist(sparseArr,size,size,sum);
        //3.2 遍历原始数组，将非0的值存放到稀疏数组中
        sparseArr = setSparseArrData(sparseArr,chessArr);



        return  sparseArr;
    }


    /**
     * 给稀疏数组赋有效数据的值
     * @param sparseArr     稀疏数组
     * @param chessArr      原始二维数组
     * @return
     */
    private static int[][] setSparseArrData(int[][] sparseArr, int[][] chessArr) {
        //用于记录是第几个非0的数据(有效数据)
        int count = 0;
        int chessArrSize = chessArr.length;
        for (int i = 0; i < chessArrSize; i++) {
            for (int j = 0; j < chessArrSize; j++) {
                //有效数据
                int validData = chessArr[i][j];
                if(validData!=0){
                    //因为稀疏数组的第一行记录的是原始数组的数据。所以，有效数据，应该是从第二行开始
                    count ++;
                    //稀疏数组中记录有效数据的行是在第0列
                    sparseArr[count][0] = i;
                    //稀疏数组中记录有效数据的列是第1列
                    sparseArr[count][1] = j;
                    //稀疏数组中记录具体有效数据是第二列
                    sparseArr[count][2] = validData;
                }
            }
        }
        System.out.println();
        System.out.println("二维数组转换成稀疏数组为");
        for (int i =  0;i<sparseArr.length;i++){
            System.out.printf("%d \t  %d \t %d \t\n ",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
        }

        return sparseArr;
    }

    /**
     * 初始化稀疏数组的第一行
     * @param sparseArr 稀疏数组
     * @param rowSize   原始数组的行数
     * @param colSize   原始数组的列数
     * @param sum       有效的个数
     * @return
     */
    private static int[][] initSparseArrFrist(int [] [] sparseArr,int rowSize,int colSize,  int sum) {
        sparseArr[0][0] = rowSize;
        sparseArr[0][1] = colSize;
        sparseArr[0][2] = sum;
        return sparseArr;
    }


    /**
     * 初始化五子棋 11*11
     * @return
     */
    public static int[][] init() {
        int chessArr[] [] = new int[11][11];
        chessArr[1][2] = 1;
        chessArr [2][3] = 2;
        //输出原始的二维数组
        System.out.println("原始的二维数组");
        for(int [] row: chessArr){
            for(int col :row){
                System.out.printf("%d\t",col);
            }
            System.out.println();
        }


        return chessArr;
    }
}
